#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
typedef long long LL;
typedef double db;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); }
	return x*f;
}
const int MAXN=4e4;
const db eps=1e-9;
int a[MAXN],aid[MAXN],tot;
inline int cmp(db x)
{
	return x<-eps?-1:(x>eps?1:0);
}
struct Seg_T
{
	db k[MAXN*5],b[MAXN*5];
	int id[MAXN*5];
	void push_down(int o,int l,int r,db K,db B,int ID)
	{
		if(!id[o])
		{
			k[o]=K;b[o]=B;id[o]=ID;
			return;
		}
		if(cmp(K-k[o])==0&&cmp(B-b[o])==0)return;
		db y1=k[o]*l+b[o],y2=K*l+B,y3=k[o]*r+b[o],y4=K*r+B;
		if(db(y2-y1)>0&&db(y4-y3)>0)
		{
			k[o]=K;b[o]=B;id[o]=ID;
			return;
		}
		if(db(y2-y1)<=0&&db(y4-y3)<=0)return;
		int mid=(l+r)>>1;
		push_down(lc,l,mid,K,B,ID);
		push_down(rc,mid+1,r,K,B,ID);
		return;
	}
	void update(int o,int l,int r,int yl,int yr,db K,db B,int ID)
	{
		if(yl<=l&&r<=yr)
		{
			push_down(o,l,r,K,B,ID);
			return;
		}
		int mid=(l+r)>>1;
		if(yl<=mid)update(lc,l,mid,yl,yr,K,B,ID);
		if(yr>mid)update(rc,mid+1,r,yl,yr,K,B,ID);
		return;
	}
	void query(int o,int l,int r,int x,db &ans,int &ID)
	{
		db y=k[o]*x+b[o];
		if(cmp(y-ans)>0||(cmp(y-ans)==0&&id[o]<ID))
		{
			ans=y;
			ID=id[o];
		}
		if(l==r)return;
		int mid=(l+r)>>1;
		if(x<=mid)query(lc,l,mid,x,ans,ID);
		else query(rc,mid+1,r,x,ans,ID);
		return;
	}
}T1;
int main()
{
	int n=read(),lstans=0;
	while(n--)
	{
		int op=read();
		if(!op)
		{
			db ans=0;
			int ID=0,x=(read()+lstans-1)%39989+1;
			T1.query(1,1,MAXN,x,ans,ID);
			if(cmp(a[x]-ans)>0||(cmp(a[x]-ans)==0&&aid[x]<ID))ID=aid[x];
			printf("%d\n",lstans=ID);
		}
		else
		{
			++tot;
			int x1=(read()+lstans-1)%39989+1,y1=(read()+lstans-1)%1000000000+1,x2=(read()+lstans-1)%39989+1,y2=(read()+lstans-1)%1000000000+1;
			if(x1>x2)swap(x1,x2),swap(y1,y2);
			if(x1==x2)
			{
				if(max(y1,y2)>a[x1])a[x1]=max(y1,y2),aid[x1]=tot;
			}
			else
			{
				db K=(db)(y2-y1)/(db)(x2-x1),B=(db)y1-K*x1;
				T1.update(1,1,MAXN,x1,x2,K,B,tot);
			}
		}
	}
	return 0;
}
